package com.azure.code.dfs.island;

/**
 * 飞地数量
 *  Number of Enclaves
 * https://leetcode-cn.com/problems/number-of-enclaves/
 */
public class Island_1020 {

    public int numEnclaves(int[][] grid) {
        int m=grid.length,n = grid[0].length;
        for (int i = 0; i < m; i++) {
            dfs(grid,i,0);
            dfs(grid,i,n-1);
        }
        for (int j = 0; j < n; j++) {
            dfs(grid,0,j);
            dfs(grid,m-1,j);
        }
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j]==1) {
                    res++; //  这里
                }
            }
        }
        return res;
    }
    private void dfs(int[][] grid, int i, int j) {
        int m = grid.length, n = grid[0].length;
        if(i<0||j<0||i>=m||j>=n||grid[i][j]==0) return;
        grid[i][j] = 0;
        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
    }

    public static void main(String[] args) {
        int[][] grid = {{0,0,0,0},{1,0,1,0},{0,1,1,0},{0,0,0,0}};
        System.out.println(new Island_1020().numEnclaves(grid));
    }
}
